package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

public class No111二叉树的最小深度 {

    /**
     * 给定一个二叉树，找出其最小深度。
     * 最小深度是从根节点到最近叶子节点!!!的最短路径上的节点数量。
     */

    int min=Integer.MAX_VALUE;

    //我写的是深度优先遍历,但是广度优先会更快,因为只要node.left==null&&node.right==null返回即可
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;

        dg(root,1);

        return min;
    }

    private void dg(TreeNode node,int deep){
        if(deep>min)
            return;
        if(node==null)
            return;
        if(node.right==null&&node.left==null)
            min=Math.min(min,deep);
        dg(node.left,deep+1);
        dg(node.right,deep+1);
    }

    //广度优先版
    public int minDepthGood(TreeNode root){
        if(root==null)
            return 0;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int deep=0;
        while (!queue.isEmpty()){
            int count=queue.size();
            deep++;
            while (count>0){
                TreeNode poll = queue.poll();
                if(poll.left==null&&poll.right==null)//不会出现poll等于null
                    return deep;
                if(poll.left!=null)
                    queue.add(poll.left);
                if(poll.right!=null)
                    queue.add(poll.right);
                count--;
            }
        }

        return deep;
    }

    public static void main(String[] args) {
        No111二叉树的最小深度 n1=new No111二叉树的最小深度();
        TreeNode nodeByArr=
                TreeNode.getNodeByArr(new Integer[]{2, null, 3, null, 4, null, 5, null, 6});
        System.out.println(n1.minDepthGood(nodeByArr));

    }

}
